You have n processes forming a rooted tree structure. You are given two integer arrays pid and ppid, where pid[i] is the ID of the ith process and ppid[i] is the ID of the ith process's parent process.
Each process has only one parent process but may have multiple children processes. Only one process has ppid[i] = 0, which means this process has no parent process (the root of the tree).
When a process is killed, all of its children processes will also be killed.
Given an integer kill representing the ID of a process you want to kill, return a list of the IDs of the processes that will be killed. You may return the answer in any order.
Example 1:
Input: pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5 Output: [5,10] Explanation: The processes colored in red are the processes that should be killed.
Example 2:
Input: pid = [1], ppid = [0], kill = 1 Output: [1]
Constraints:
n == pid.lengthn == ppid.length1 <= n <= 5 * 1041 <= pid[i] <= 5 * 1040 <= ppid[i] <= 5 * 104- Only one process has no parent.
- All the values of
pidare unique. killis guaranteed to be inpid.
Average Rating: 4.75 (24 votes)
Video Solution
Solution Article
Approach #1 Depth First Search [Time Limit Exceeded]
Algorithm
Since killing a process leads to killing all its children processes, the simplest solution is to traverse over the ppid array and find out all the children of the process to be killed. Further, for every child chosen to be killed we recursively make call to the killProcess function now treating this child as the new parent to be killed. In every such call, we again traverse over the ppid array now considering the id of the child process, and continue in the same fashion. Further, at every step, for every process chosen to be killed, it is added to the list l that needs to be returned at the end.
Complexity Analysis
-
Time complexity : O(nn). O(nn) function calls will be made in the worst case
-
Space complexity : O(n). The depth of the recursion tree can go upto n.
Approach #2 Tree Simulation [Accepted]
Algorithm
We can view the given process relationships in the form of a tree. We can construct the tree in such a way that every node stores information about its own value as well as the list of all its direct children nodes. Thus, now, once the tree has been generated, we can simply start off by killing the required node, and recursively killing the children of each node encountered rather than traversing over the whole ppid array for every node as done in the previous approach.
In order to implement this, we've made use of a Node class which represents a node of a tree. Each node represents a process. Thus, every node stores its own value(Node.val) and the list of all its direct children(Node.children). We traverse over the whole pid array and create nodes for all of them. Then, we traverse over the ppid array, and make the parent nodes out of them, and at the same time add all their direct children nodes in their Node.children list. In this way, we convert the given process structure into a tree structure.
Now, that we've obtained the tree structure, we can add the node to be killed to the return list l. Now, we can directly obtain all the direct children of this node from the tree, and add its direct children to the return list. For every node added to the return list, we repeat the same process of obtaining the children recursively.
Complexity Analysis
-
Time complexity : O(n). We need to traverse over the ppid and pid array of size n once. The
getAllChildrenfunction also takes atmost n time, since no node can be a child of two nodes. -
Space complexity : O(n). map of size n is used.
Approach #3 HashMap + Depth First Search [Accepted]
Algorithm
Instead of making the tree structure, we can directly make use of a data structure which stores a particular process value and the list of its direct children. For this, in the current implementation, we make use of a hashmap map, which stores the data in the form parent:[listofallitsdirectchildren].
Thus, now, by traversing just once over the ppid array, and adding the corresponding pid values to the children list at the same time, we can obtain a better structure storing the parent-children relationship.
Again, similar to the previous approach, now we can add the process to be killed to the return list, and keep on adding its children to the return list in a recursive manner by obtaining the child information from the structure created previously.
-
Time complexity : O(n). We need to traverse over the ppid array of size n once. The
getAllChildrenfunction also takes atmost n time, since no node can be a child of two nodes. -
Space complexity : O(n). map of size n is used.
Approach #4 HashMap + Breadth First Search [Accepted]:
Algorithm
We can also make use of Breadth First Search to obtain all the children(direct+indirect) of a particular node, once the data structure of the form (process:[listofallitsdirectchildren] has been obtained. The process of obtaining the data structure is the same as in the previous approach.
In order to obtain all the child processes to be killed for a particular parent chosen to be killed, we can make use of Breadth First Search. For this, we add the node to be killed to a queue. Then, we remove an element from the front of the queue and add it to the return list. Further, for every element removed from the front of the queue, we add all its direct children(obtained from the data structure created) to the end of the queue. We keep on doing so till the queue becomes empty.
Complexity Analysis
-
Time complexity : O(n). We need to traverse over the ppid array of size n once. Also, atmost n additions/removals are done from the queue.
-
Space complexity : O(n). map of size n is used.
Last Edit: September 7, 2018 11:17 AM
I think the time complexity for first approach is n^2, because there is no repetition nodes which are already explored during the search process.
I feel like you should also mention that a simple topological sort from the 'kill' node generates the answer - particularly Approach #3 does basically just that.
September 23, 2019 3:43 PM
Should be an easy problem
November 5, 2018 4:28 AM
can someone explain why the brute force approach (#1) runtime is O(n^n)?
The time complexity for the first approach should be O(n^2) or otherwise, I just don't know what I am doing here!
Easy to understand Python3 Solution using Hashmap and Queue:
def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
children_map = defaultdict(list)
for i in range(len(pid)):
if ppid[i] != 0:
children_map[ppid[i]].append(pid[i])
queue = [kill]
res = []
while queue:
curr_process = queue.pop()
res.append(curr_process)
if curr_process in children_map:
for p in children_map[curr_process]:
queue.append(p)
children_map[curr_process] = []
return res
List < Integer > l = new ArrayList < > ();
if (kill == 0)
return l;
l.add(kill);
for (int i = 0; i < ppid.size(); i++)
if (ppid.get(i) == kill)
l.addAll(killProcess(pid, ppid, pid.get(i)));
return l;
This code is wrong as if we are killing 0 then it will return an empty list, but since 0 is the root process, ideally all process should be in the result.
if (kill == 0)
return l;
I do not think that this base case is required. The recursion will stop if none of the ppid.get(i) is equal to kill.
Correct version:
List < Integer > l = new ArrayList < > ();
l.add(kill);
for (int i = 0; i < ppid.size(); i++)
if (ppid.get(i) == kill)
l.addAll(killProcess(pid, ppid, pid.get(i)));
return l;
I was also thinking if it can be done like, find the node that needs to be killed. Then mark that with respect to its parent as null, (e.g. in this 5 is the node to be killed so mark 2's left to be null ) but save that tree in a temporary node, say temp. After that just traverse using one of the traversal and add the nodes to be printed in an array or list and print them. How about this?
June 1, 2017 3:38 PM
@mrvon @aprilyin Sorry there was some problem. We have fixed it. Thanks
June 1, 2017 1:59 PM
It seems mismatching answer and problem.
xxxxxxxxxxclass Solution {public: // BFS + Hashmap vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) { vector<int> res; unordered_map<int, vector<int>> mp; // add childrens id of every node as value in map with parent id as key for(int i=0;i<ppid.size();i++) { if(ppid[i] > 0) { mp[ppid[i]].push_back(pid[i]); } } queue<int>q; q.push(kill); while(!q.empty()) { int parent = q.front(); q.pop(); res.push_back(parent); if(mp.find(parent) != mp.end()) { for(int child : mp[parent]) q.push(child); } } return res; }};